package com.hash;

import com.avl.AVLTree;
import com.map.BSTMap;
import com.rbt.RBTree;
import com.set.FileOperation;

import java.util.ArrayList;
import java.util.TreeMap;

/**
 * 自己实现一个哈希表
 * @param <K>
 * @param <V>
 */
public class HashTable<K, V> {

    /**
     * TreeMap的底层是红黑树，用这个来处理哈希冲突的情况
     */
    private TreeMap<K, V>[] hashtable;
    private int M;
    private int size;

    public HashTable(int M) {
        this.M = M;
        size = 0;
        hashtable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashtable[i] = new TreeMap<>();
        }
    }
    public HashTable() {
        this(100);
    }

    /**
     * 将传入的关键字转化hash表中的索引
     * @param key
     * @return
     */
    private int hash(K key) {
        return  (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        TreeMap<K, V> map = hashtable[hash(key)];
        if (map.containsKey(key)) {
            map.put(key, value);
        }else {
            map.put(key, value);
            size ++;
        }
    }

    public V remove(K key) {
        TreeMap<K, V> map = hashtable[hash(key)];
        V ret = null;
        if (map.containsKey(key)) {
            ret = map.remove(key);
            size --;
        }
        return ret;
    }

    public void set(K key, V value) {
        TreeMap<K, V> map = hashtable[hash(key)];
        if (!map.containsKey(key)) {
           throw new IllegalArgumentException("Key doesn't exist!");
        }
        map.put(key, value);
    }

    public boolean contains(K key) {
         return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key) {
        return hashtable[hash(key)].get(key);
    }

    public static void main(String[] args) {

        System.out.println("Test with book: pride-and-prejudice");
        String filePath = "E:\\WorkSpace\\LearningDemoWorkSpace\\data-structure\\src\\pride-and-prejudice.txt";
        ArrayList<String> words = new ArrayList<>();
        if (FileOperation.readFile(filePath, words)) {
            System.out.println("Total words: " + words.size());

            // BST tree
            long startTime = System.nanoTime();
            BSTMap<String, Integer> bst = new BSTMap<>();
            for (String word : words) {
                if (bst.contains(word)) {
                    bst.set(word, bst.get(word) + 1);
                } else {
                    bst.add(word, 1);
                }
            }
            long endTime = System.nanoTime();
            double time1 = (endTime - startTime) / 1000000000.0;
            System.out.println("BST time: " + time1 + " s");

            // AVL tree
            long startTime02 = System.nanoTime();
            AVLTree<String, Integer> avlTree = new AVLTree<>();
            for (String word : words) {
                if (avlTree.contains(word)) {
                    avlTree.set(word, avlTree.get(word) + 1);
                } else {
                    avlTree.add(word, 1);
                }
            }
            long endTime02 = System.nanoTime();
            double time2 = (endTime02 - startTime02) / 1000000000.0;
            System.out.println("AVL time: " + time2 + " s");

            System.out.println();
            // RBT tree
            long startTime03 = System.nanoTime();
            RBTree<String, Integer> rbTree = new RBTree<>();
            for (String word : words) {
                if (rbTree.contains(word)) {
                    rbTree.set(word, rbTree.get(word) + 1);
                } else {
                    rbTree.add(word, 1);
                }
            }
            long endTime03 = System.nanoTime();
            double time3 = (endTime03 - startTime03) / 1000000000.0;
            System.out.println("RBT time: " + time3 + " s");

            System.out.println();
            // hash table
            long startTime04 = System.nanoTime();
            HashTable<String, Integer> hashTable = new HashTable<>(130000);
            for (String word : words) {
                if (hashTable.contains(word)) {
                    hashTable.set(word, hashTable.get(word) + 1);
                } else {
                    hashTable.add(word, 1);
                }
            }
            long endTime04 = System.nanoTime();
            double time4 = (endTime04 - startTime04) / 1000000000.0;
            System.out.println("HashTable time: " + time4 + " s");
        }
    }

}

